From Domination to Coloring by Gary Chartrand & Teresa W. Haynes & Michael A. Henning & Ping Zhang

Author:Gary Chartrand & Teresa W. Haynes & Michael A. Henning & Ping Zhang
Language: eng
Format: epub
ISBN: 9783030311100
Publisher: Springer International Publishing

Theorem 4.3.5

([10]) If T is a tree, then .

Proof

Let T be a tree of order n. We proceed by induction on n. Note that if T is the trivial graph or the star , then , and if T is the double star (where ), then . Hence, we can assume that . This implies that and .

Assume that any tree with order has .

Let r and v be two vertices at apart, and root T at r. Necessarily, r and v are leaves of T. Let u be the parent of v, w the parent of u, and x the parent of w. Note that by our choice of v, u is a terminal support vertex in T. If w has degree 2, then is a distribution center of T implying that .

Hence, we can assume that the degree of w is at least 3. By our choice of u, every child of w is either a leaf or a terminal support vertex. Let . Let D be a minimum dominating set of T containing the support vertices of T (which is always possible since either the support vertex or its adjacent leaves must be in every dominating set), and let be a restriction of D onto . Since u is a support vertex of T, we can assume that u is in D. If w has a leaf neighbor, then w is in D; otherwise w is dominated by a child in that is a support vertex. Hence, is a dominating set of and so .

Let be a -set of . If , then is a distribution center of T. Thus, , as desired. Hence, assume that . But then is a distribution center of T. Therefore, , and the result follows.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.